#include <iostream>
#include <cstring>
using namespace std;

int a[2000000];
int b[2000000];
int src[10000];
struct data{
	int value;
	int distance;
};

data result[10000];
int num_result=0;
int num=1;

void handle(int k);
void output();
int main()
{
	memset(a,0,sizeof(a));
	a[0]=1;
	a[1]=1;
	for(int i=2;i<2000000;i++){
		for(int j=2;j<2000000&&i*j<2000000;j++){
			a[i*j]=1;
		}
	}
	for(int k=0;k<2000000;k++){
		if(a[k]==0) {
			b[num]=k;
			num++;
		}
	}
	
	int n;
	cin>>n;
		for(int i=0;i<n;i++) cin>>src[i];
		handle(n);
		output();
		num_result=0;

	
	return 0;
}

void handle(int k)
{
	for(int i=0;i<k;i++){
		if(src[i]<=2){
			result[num_result].value=2;
			result[num_result].distance=2-src[i];
			num_result++;
			continue;
		}
		if(src[i]>=b[num-1]){
			result[num_result].value=b[num-1];
			result[num_result].distance=src[i]-b[num-1];
			num_result++;
			continue;
		}
		for(int j=1;j<num-1;j++){
			
			if(src[i]>=b[j]&&src[i]<=b[j+1]){
				int d1=src[i]-b[j];
				int d2=b[j+1]-src[i];
				
				if(d1<d2){
					result[num_result].value=b[j];
					result[num_result].distance=d1;
					num_result++;
					break;
				}
				else{
					result[num_result].value=b[j+1];
					result[num_result].distance=d2;
					num_result++;
					break;
				}
			}
		}
		
		
	}
}

void output(){
	for(int i=0;i<num_result;i++){
		cout<<result[i].value<<endl;
	}
	
}


